平面图

一.定义
若能将无向图 G=(V,E)G=(V,E) 画在平面上使得任意两条无重合顶点的边不相交,则称 GG 是平面图。

在平面图中,由边构成的最小区域称为面,包围该面的边数记为该面的度,特殊的,平面图外的区域也为一个面。

比如图一不是平面图,图二因为和图三等价,是平面图。

二.性质

  1. 平面图的面的度的和等于边数的两倍
    显然。

  2. 欧拉公式:对于联通平面图,ve+r=2v−e+r=2, 其中 vv 为点数 , ee 为边数 , rr 为面数
    证明:

e=1e=1 ,因为图联通,所以 v=2,r=1v=2,r=1 ,成立。

ee 进行数学归纳,若 e=ie=i 成立,那么对于第 i+1i+1 条边

  • 两端均为连通块的点,那么便会增加一个面,点数不变。
  • 一端为连通块的点,另一端为不在连通块内的点,那么会增加一个点,面数不变。
    所以结论成立。

推论:对于任意平面图,ve+r=k+1v−e+r=k+1kk 为平面图的连通块个数
e=0e=0,那么 v=k,r=1v=k,r=1 , 成立。

ee 进行数学归纳,若 e=ie=i 成立,那么对于第 i+1i+1 条边

  • 两端的点属于一个连通块,那么便会增加一个面。
  • 两端的点不属于一个连通块,那么便会减少一个连通块。
    所以结论成立。

3.当 v3v≥3 ,平面图的边数不大于 3v63v−6
一个面至少有三条边,那么平面图的面的度的和至少为 3r3r

又由 (1)(1) 得平面图的面的度的和为 2e2e

所以 :2e3r2e≥3r

代入欧拉公式得:

2e3r=3(2+ev)=6+3e3v2e≥3r=3(2+e−v)=6+3e−3v

e63v−e≥6−3v

e3v6e≤3v−6

三.例题
1.P3209 [HNOI2010]平面图判定